/*
 * GRASP.cpp
 *
 *  Created on: 21/06/2011
 *      Author: daniel
 */

#include "GRASP.h"
#include "Operator.h"
#include "LS.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <float.h>
using namespace std;

typedef struct edge {
	int a;
	int b;
	double cost;
} Edge;

class CompCities {
public:
	Solution *s;
	int currentCity;

	CompCities(Solution *s, int currentCity) {
		this->s = s;
		this->currentCity = currentCity;
	}

	bool operator()(int i, int j) {
		return (s->getCostByCity(i, currentCity) < s->getCostByCity(j,
				currentCity));
	}
};

Edge* newEdge(int a, int b, double cost) {
	Edge *e = (Edge*) malloc(sizeof(Edge));

	e->a = a;
	e->b = b;
	e->cost = cost;

	return e;
}

bool compareEdge(Edge *e1, Edge *e2) {

	if (e1 == NULL || e2 == NULL)
		cout << "Error en compareEdge, lados nulos\n";

	if (e1->cost < e2->cost)
		return true;
	return false;
}

bool compareInt(int i, int j) {
	return (i < j);
}

void print(vector<Edge*> v) {

	printf("[(%d,%d,%f)", v[0]->a, v[0]->b, v[0]->cost);
	for (int i = 1; i < v.size(); ++i)
		printf(", (%d,%d,%f)", v[i]->a, v[i]->b, v[i]->cost);

	cout << "]\n";
}

void print(vector<int> v) {
	printf("[%d", v[0]);
	for (int i = 1; i < v.size(); ++i)
		printf(", %d", v[i]);

	cout << "]\n";
}

void rmv(vector<Edge*> *candidates, Edge *e) {

	for (int i = 0; i < candidates->size(); ++i) {
		if (candidates->at(i) == e) {
			free(candidates->at(i));
			candidates->erase(candidates->begin() + i);
			break;
		}
	}
}

/**
 * Obtiene la ciudad mas cercana de un conjunto de ciudades.
 */
int getCheapest(Solution *problem, int current, vector<int> cities) {

	double lowestCost = DBL_MAX;
	int best;

	for (int i = 0; i < cities.size(); ++i) {
		double currentCost = problem->getCostByCity(current, cities[i]);

		// Si encontro la mas barata.
		if (currentCost < lowestCost) {
			best = cities[i];
			lowestCost = currentCost;
		}
	}
	return best;
}

/*
 * Retorna un conjunto de los arcos mas baratos.
 */
vector<Edge*> buildRCL(vector<Edge*> candidates, double alpha) {

	vector<Edge*> RCL;
	double cMin = candidates.front()->cost;
	double cMax = candidates.back()->cost;

	for (int i = 0; i < candidates.size(); ++i) {
		Edge *e = candidates[i];

		if (alpha >= 0 && alpha < 1) {
			if (e->cost <= cMin + alpha * (cMax - cMin))
				RCL.push_back(e);
		} else if (alpha > 1) {
			RCL.push_back(e);
			alpha--;
		} else
			break;
	}
	return RCL;
}

/**
 * Retorna un conjunto de las ciudades mas cercanas.
 */
vector<int> buildRCL(Solution *s, vector<int> cities, int currentCity,
		double alpha) {

	vector<int> RCL;
	sort(cities.begin(), cities.end(), CompCities(s, currentCity));

	double cMin = s->getCostByCity(cities.front(), currentCity);
	double cMax = s->getCostByCity(cities.back(), currentCity);

	for (int i = 0; i < cities.size(); ++i) {

		// Costo de ir de la ciudad i a la actual.
		double currentCost = s->getCostByCity(cities[i], currentCity);

		if (currentCost <= cMin + alpha * (cMax - cMin)) {
			//printf("currentCost:%f, bound:%f\n", currentCost, cMin + alpha * (cMax - cMin));
			RCL.push_back(cities[i]);
		}
	}
	return RCL;
}

vector<Edge*> InitializeCandidates(Solution *problem) {

	vector<Edge*> candidates;

	for (int i = 1; i <= problem->cityNumber; ++i) {
		for (int j = i + 1; j <= problem->cityNumber; ++j) {

			Edge *e = newEdge(i, j, problem->C[i - 1][j - 1]);
			candidates.push_back(e);
		}
	}

	// Ordena los candidatos segun el costo.
	sort(candidates.begin(), candidates.end(), compareEdge);

	return candidates;
}

Edge* selectEdge(vector<Edge*> RCL) {

	//srand(time(NULL));
	int index = rand() % RCL.size();

	return RCL[index];
}

double evalSolution(Solution *s) {

	double cost;
	int i;
	for (i = 0; i < s->cityNumber - 1; i++) {
		cost += s->getCost(i, i + 1);
	}
	cost += s->getCost(i, 0);

	return cost;
}

Solution *GRASP::GreedyRandomizedConstruction(Solution *problem, double alpha) {

	Solution *s = new Solution(problem->cityNumber);
	vector<Edge*> candidates = InitializeCandidates(problem);

	s->C = problem->C;
	int i = 0;
	while (!candidates.empty() && i < problem->cityNumber) {

		vector<Edge*> RCL = buildRCL(candidates, alpha);
		Edge *e = selectEdge(RCL);

		if (s->addCity(e->a) != -1)
			i++;
		if (s->addCity(e->b) != -1)
			i++;

		// Actualizar candidatos y limpia RCL.
		rmv(&candidates, e);
		RCL.clear();
	}

	// Calcula el costo de esta solucion.
	s->cost = evalSolution(s);

	return s->clone();
}

/**
 * Obtiene una solucion greedy completamente.
 * @param: Una definicion de problema.
 * @return: Una solucion completamente greedy.
 */
Solution *GRASP::SampleGreedy(Solution *problem, double alpha) {

	// Obtiene la ciudad inicial de forma
	// aleatoria.
	//srand(time(NULL));
	int initialCity = (rand() % problem->cityNumber) + 1;

	// Construye un arreglo de ciudades.
	vector<int> cities;
	for (int i = 1; i <= problem->cityNumber; ++i)
		cities.push_back(i);

	// Crea la solucion a ser llenada.
	Solution *s = new Solution(problem->cityNumber);
	s->C = problem->C;
	s->addCity(initialCity); // Agrega la ciudad inicial.

	// Elimina la ciudad inicial del arreglo de
	// ciudades.
	cities.erase(find(cities.begin(), cities.end(), initialCity));

	int current = 0;
	while (!cities.empty()) {

		// Obtiene la lista de las n mejores ciudades.
		vector<int> RCL = buildRCL(problem, cities, s->tour[current], alpha);

		// Elige una aleatoriamente.
		//srand(time(NULL));
		int randomCity = RCL[(rand() % RCL.size())];

		// La agrega al tour.
		s->addCity(randomCity);

		// La elimina de las ciudades desponibles y borra la RCL.
		cities.erase(find(cities.begin(), cities.end(), randomCity));
		RCL.clear();

	}
	//s->print();
	s->cost = evalSolution(s);

	return s->clone();
}

/**
 * Obtiene una solucion greedy completamente.
 * @param: Una definicion de problema.
 * @return: Una solucion completamente greedy.
 */
Solution *GRASP::Greedy(Solution *problem, double alpha) {

	// Obtiene la ciudad inicial de forma
	// aleatoria.
	//srand(time(NULL));
	int initialCity = (rand() % problem->cityNumber) + 1;

	// Construye un arreglo de ciudades.
	vector<int> cities;
	for (int i = 1; i <= problem->cityNumber; ++i)
		cities.push_back(i);

	// Crea la solucion a ser llenada.
	Solution *s = new Solution(problem->cityNumber);
	s->C = problem->C;
	s->addCity(initialCity); // Agrega la ciudad inicial.

	// Elimina la ciudad inicial del arreglo de
	// ciudades.
	cities.erase(find(cities.begin(), cities.end(), initialCity));

	int current = 0;
	while (!cities.empty()) {

		int bestPos = 0;
		double lowestCost = DBL_MAX;

		for (int i = 0; i < cities.size(); ++i) {

			double currentCost = s->getCostByCity(s->tour[current], cities[i]);

			// Si encontro la mas barata.
			if (currentCost < lowestCost) {
				bestPos = i;
				lowestCost = currentCost;
			}
		}
		s->addCity(cities[bestPos]);
		cities.erase(cities.begin() + bestPos);
		current++;
	}

	s->cost = evalSolution(s);
	return s;
}

Solution *GRASP::Grasp(Solution *problem, int MaxIter, double alpha,
		int maxStuck, int greedy) {

	int k = 0;
	Solution *sOpt = problem->clone();
	Solution *sAct;

	while (k < MaxIter) {

		if (greedy == 1)
			sAct = SampleGreedy(problem, alpha);
		else if (greedy == 2)
			sAct = Greedy(problem, alpha);
		else if (greedy == 3)
			sAct = GreedyRandomizedConstruction(problem, alpha);

		sAct = LS::LocalSearchBI(sAct, 10000000, maxStuck);

		if (sAct->cost < sOpt->cost) {
			delete sOpt;
			sOpt = sAct->clone();
		}

		delete sAct;
		k++;
	}

	sOpt->iniCost = problem->cost;
	sOpt->numIter = k;

	return sOpt;
}
